#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""

class RandomListNode:
    def __init__(self, x, next=None):
        self.label = x
        self.next = next
        self.random = None


class Solution:
    def copyRandomList(self, head):
        if not head:
            return head

        self.hash = {  }        # { originNode : newNode }
        self.head = head

        self.double(head)
        return self.copy_random()
        # return self.disconnect()

    def double(self, head):
        node = head

        while node:
            copy_peer = RandomListNode(node.label)
            self.hash[node] = copy_peer

            # node_next = node.next
            node = node.next

        self.hash[None] = None

    def copy_random(self):
        print('copy')
        node = self.head
        copy_head = self.hash[node]
        peer_node = copy_head

        while node:
            ori_next = node.next
            peer_next = self.hash[ori_next]

            peer_node.next = peer_next

            # if node.random:
            peer_node.random = self.hash[node.random]

            node = ori_next
            peer_node = peer_next

        return copy_head


def main():
    print("start main")

    v5 = RandomListNode(10)
    v4 = RandomListNode(8, v5)
    v3 = RandomListNode(6, v4)
    v2 = RandomListNode(4, v3)
    v1 = RandomListNode(2, v2)
    vm = RandomListNode(1, v1)


    s = Solution()
    ret = s.copyRandomList(vm)
    print(ret.label)
    print(ret.next.label)
    print(ret.next.next.label)


if __name__ == "__main__":
    main()
